package com.atguigui.leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 946.验证栈序列
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/8/31 14:57
 */
public class P946ValidateStackSequences {

    public static void main(String[] args) {
        Solution solution = new P946ValidateStackSequences().new Solution();
        // TO TEST
    }

    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> stack = new ArrayDeque<Integer>();
            int n = pushed.length;
            for (int i = 0, j = 0; i < n; i++) {
                stack.push(pushed[i]);
                while (!stack.isEmpty() && stack.peek() == popped[j]) {
                    stack.pop();
                    j++;
                }
            }
            return stack.isEmpty();
        }
    }
}
